#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    long long my_power(long long num, int x) {
        int number = num;
        while (--x) num *= number;
        return num;
    }
    int numberOfWays(int n, int x) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        long long pathmax = 0, mod = 1e9 + 7;
        for (int i = 1; i <= n; i++) {
            long long tmp = my_power(i, x);
            pathmax = min(pathmax + tmp, (long long)n);
            for (int j = pathmax; j >= tmp; j--) {
                if (dp[j - tmp]) dp[j] = (dp[j] + dp[j - tmp]) % mod;
            }
            // for(int j = 0; j <= n; j++) cout << dp[j] << ' ';
            // cout << endl; 
        }
        return dp[n];
    }
};